package top100.tree;

import top100.linklist.Solution234;
import utils.TreeNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/26 8:31
 * @description:
 */
public class Solution437 {
    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        int res = rootSum(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    public int rootSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        int ret = 0;
        if (root.val == targetSum) {
            ret++;//子节点可能为0
        }
        ret += rootSum(root.left, targetSum - root.val);
        ret += rootSum(root.right, targetSum - root.val);
        return ret;
    }

    public static void main(String[] args) {
        Solution437 solution = new Solution437();
        int[] nums = {10, 5, -3, 3, 2, Integer.MAX_VALUE, 11, 3, -2, Integer.MAX_VALUE, 1};
        TreeNode root = TreeNode.buildTree(nums, Integer.MAX_VALUE);
        TreeNode.show(root);
        System.out.println(solution.pathSum(root, 8));//3

        nums = new int[]{5, 4, 8, 11, Integer.MAX_VALUE, 13, 4, 7, 2, Integer.MAX_VALUE, Integer.MAX_VALUE, 5, 1};
        TreeNode root2 = TreeNode.buildTree(nums, Integer.MAX_VALUE);
        TreeNode.show(root2);
        System.out.println(solution.pathSum(root2, 22));//3

        nums = new int[]{10, 5, -3, 3, 2, Integer.MAX_VALUE, 11, 0, 1, Integer.MAX_VALUE, 1, Integer.MAX_VALUE,
                0, 0, Integer.MAX_VALUE, 0, 0, 0, Integer.MAX_VALUE, 1, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 0};
        TreeNode root3 = TreeNode.buildTree(nums, Integer.MAX_VALUE);
        TreeNode.show(root3);
        System.out.println(solution.pathSum(root3, 8));//8

        nums = new int []{1000000000,1000000000,Integer.MAX_VALUE,294967296,Integer.MAX_VALUE,1000000000,Integer.MAX_VALUE,1000000000,Integer.MAX_VALUE,1000000000};
        TreeNode root4 = TreeNode.buildTree(nums, Integer.MAX_VALUE);
        TreeNode.show(root4);
        System.out.println(solution.pathSum(root4, 0));//0  溢出问题
    }
}
